import java.net.DatagramPacket;
import java.net.SocketException;
import java.util.ArrayList;
import java.util.TreeMap;
import java.util.HashSet;

public class lsnode
{
    int localPort;
    final String localhost = "127.0.0.1";
    TreeMap<Integer, Integer> neighbours = new TreeMap<Integer, Integer>();
    TreeMap<Integer, Boolean> verified = new TreeMap<Integer, Boolean>();
    TreeMap<Integer, TreeMap<Integer, Integer>> recvedDVec = new TreeMap<Integer, TreeMap<Integer, Integer>>();
    TreeMap<Integer, Integer> routingTable = new TreeMap<Integer, Integer>();
    boolean selfBroadcasted = false;
    boolean verifyFinished = false;
    boolean isLast;
    final int bufferSize = 1024;
    int longestDest;

    UDPWrapper port;

    /**
     * Thread to wait 5 seconds, print graph and build table. Then wait 10s
     * before exiting.
     * 
     * @author Jiabin
     */
    class WaitToBuildTable implements Runnable
    {
        @Override
        public void run()
        {
            try
            {
                Thread.sleep(5 * 1000);
                System.out.println("Message flooding ended.");
                printGraph();
                buildTable();
                Thread.sleep(10 * 1000);
                System.exit(0);
            }
            catch (InterruptedException e)
            {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }

        }
    }

    /**
     * Thread to wait for ACK of verification request. If ACK doesn't arrive
     * during the time slot, it deems the node unreachable and notify other
     * nodes before quitting.
     * 
     * @author Jiabin
     * 
     */
    class WaitVerifyACK implements Runnable
    {
        int neighbour;

        WaitVerifyACK(int neighbour)
        {
            this.neighbour = neighbour;
        }

        @Override
        public void run()
        {
            try
            {
                Thread.sleep(2 * 1000);
                boolean neibourVerified;
                synchronized (verified)
                {
                    neibourVerified = verified.get(neighbour);
                }
                if (!neibourVerified)
                {
                    String errMsg = String
                            .format("Node (Port %d) can not reach Node (Port %d)\n", localPort, neighbour);
                    errMsg += "Link failure occurred. Program terminated.";
                    notifyError(errMsg);
                    System.out.println(errMsg);
                    System.exit(1);
                }
            }
            catch (InterruptedException e)
            {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
    }

    /**
     * Background listener thread, monitors the port and dispatches received
     * packets.
     * 
     * @author Jiabin
     */
    class Listener implements Runnable
    {
        lsnode self;

        public Listener(lsnode self)
        {
            this.self = self;
        }

        @Override
        public void run()
        {
            while (true)
            {
                byte[] buffer = new byte[bufferSize];
                DatagramPacket rawPacket = new DatagramPacket(buffer, bufferSize);
                port.receive(rawPacket);
                Packet packet = (Packet) Utility.deserializeObj(rawPacket.getData());
                switch (packet.type)
                {
                case DVec:
                {
                    DVec dvec = (DVec) packet.data;
                    if (!recvedDVec.containsKey(dvec.source))
                    {
                        recvedDVec.put(dvec.source, dvec.neighbours);
                        flood(packet);

                        if (!selfBroadcasted)
                        {
                            broadcastDVec();

                            new Thread(new WaitToBuildTable()).start();
                        }
                    }
                    break;
                }
                case Data:
                {
                    int dest = (Integer) packet.data;
                    if (dest != localPort)
                        port.send(packet, localhost, routingTable.get(dest));
                    System.exit(0);
                    break;
                }
                case Verify:
                {
                    int dist = (Integer) packet.data;
                    int src = rawPacket.getPort();
                    if (neighbours.get(src) == dist)
                    {
                        synchronized (verified)
                        {
                            verified.put(src, true);
                        }
                        port.send(new Packet(Packet.PacketType.VerifyACK, null), localhost, src);
                    }
                    else
                    {
                        String errMsg = String.format("Link cost from Node (Port %d) to Node (Port %d) is %d.\n",
                                src, localPort, dist);
                        errMsg += String.format("Link cost from Node (Port %d) to Node (Port %d) is %d.\n",
                                localPort, src, neighbours.get(src));
                        errMsg += "Link cost does not match. Program terminated.";
                        notifyError(errMsg);
                        System.out.println(errMsg);
                        System.exit(1);
                    }
                    if (!verifyFinished)
                        verify();
                    break;
                }
                case VerifyACK:
                {
                    int src = rawPacket.getPort();
                    synchronized (verified)
                    {
                        verified.put(src, true);
                    }
                    break;
                }
                case Error:
                {
                    flood(packet);
                    System.out.println(packet.data);
                    System.exit(1);
                }
                }
            }
        }
    }

    /**
     * Notify all neighbours about error.
     * 
     * @param errMsg
     *            A description of the error.
     */
    void notifyError(String errMsg)
    {
        Packet packet = new Packet(Packet.PacketType.Error, errMsg);
        flood(packet);
    }

    /**
     * Print out the received graph
     */
    void printGraph()
    {
        System.out.println("Node (Port " + localPort + ") received the following link-state information:");
        for (int port : recvedDVec.keySet())
        {
            System.out.print("source Node (Port " + port + "): ");
            for (int neighbour : recvedDVec.get(port).keySet())
            {
                System.out.print("Neighbour Node (Port " + neighbour + ") (Cost " + recvedDVec.get(port).get(neighbour)
                        + ") ");
            }
            System.out.println();
        }
    }

    /**
     * Flood packet to all its neighbours.
     * 
     * @param packet
     *            Packet to flood to all its neighbours
     */
    public void flood(Packet packet)
    {
        for (int neighbour : neighbours.keySet())
        {
            port.send(packet, localhost, neighbour);
        }
    }

    /**
     * Broadcast its own links to neighbours.
     */
    public void broadcastDVec()
    {
        System.out.println("Message flooding started.");
        DVec dvec = new DVec(localPort, neighbours);
        Packet packet = new Packet(Packet.PacketType.DVec, dvec);
        selfBroadcasted = true;
        flood(packet);
    }

    public static void main(String[] args)
    {
        lsnode self = null;
        try
        {
            self = new lsnode(args);
        }
        catch (Exception e)
        {
            System.out.println("Invalid command line arguments. Exiting...");
            System.exit(1);
        }

        self.run();
    }

    /**
     * Entry point of the program.
     */
    public void run()
    {
        Listener listener = new Listener(this);
        Thread listeningthread = new Thread(listener);
        listeningthread.start();

        if (isLast)
        {
            verify();
            try
            {
                Thread.sleep(5 * 1000);
            }
            catch (InterruptedException e1)
            {
                // TODO Auto-generated catch block
                e1.printStackTrace();
            }
            broadcastDVec();
            new Thread(new WaitToBuildTable()).start();
            try
            {
                Thread.sleep(8 * 1000);
            }
            catch (InterruptedException e)
            {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
            sendData(longestDest);
        }
        while (true)
            ;
    }

    /**
     * Send a data packet to a certain destination.
     * 
     * @param dest
     *            The destination, represented by its port number.
     */
    private void sendData(int dest)
    {
        Packet packet = new Packet(Packet.PacketType.Data, dest);
        port.send(packet, localhost, routingTable.get(dest));
        System.exit(0);
    }

    /**
     * Run Dijkstra's algorithm, calculate the shortest path.
     */
    public void buildTable()
    {
        System.out.println("Node (Port " + localPort + ") starts routing table construction");
        Vertex[] vertices = new Vertex[recvedDVec.size()];
        int i = 0;
        for (int port : recvedDVec.keySet())
        {
            vertices[i] = new Vertex(port);
            if (port == localPort)
                vertices[i].distance = 0;
            i++;
        }
        System.out.print("Step\tAdded\t");
        for (i = 0; i < vertices.length; i++)
            System.out.print("Vertex\tDist\tParent\t");
        System.out.println();
        for (i = 0; i < vertices.length; i++)
        {
            Vertex min = vertices[findMin(vertices)];
            if (i == vertices.length - 1)
                longestDest = min.port;
            min.visited = true;
            System.out.print((i + 1) + "\t" + min.port + "\t");

            TreeMap<Integer, Integer> minNeighbours = recvedDVec.get(min.port);
            for (int neighbour : minNeighbours.keySet())
            {
                int index = findPort(vertices, neighbour);
                if (vertices[index].distance == -1
                        || vertices[index].distance > min.distance + minNeighbours.get(neighbour))
                {
                    vertices[index].distance = min.distance + minNeighbours.get(neighbour);
                    vertices[index].parent = min.port;
                }
            }
            for (Vertex v : vertices)
            {
                System.out.print(v.port + "\t" + v.distance + "\t" + v.parent + "\t");
            }

            System.out.println();
        }

        for (Vertex v : vertices)
            if (v.port != localPort)
                routingTable.put(v.port, findNext(vertices, v));

        printRoutingTable();
    }

    /**
     * Print out the routing table.
     */
    private void printRoutingTable()
    {
        System.out.println();
        System.out.println("------Routing Table-------");
        System.out.println("Dest\tNext");
        for (int port : routingTable.keySet())
        {
            System.out.println(port + "\t" + routingTable.get(port));
        }
    }

    /**
     * Recursively find the next hop of a certain destination.
     * 
     * @param vertices
     *            The result of buildTable()
     * @param v
     *            Destination
     * @return The port number of next hop.
     */
    private int findNext(Vertex[] vertices, Vertex v)
    {
        if (v.parent == localPort)
            return v.port;
        else if (routingTable.containsKey(v.parent))
            return routingTable.get(v.parent);
        else
        {
            return findNext(vertices, vertices[findPort(vertices, v.parent)]);
        }
    }

    /**
     * Helper function for buildTable()
     * 
     * @param vertices
     * @param port
     * @return
     */
    private int findPort(Vertex[] vertices, int port)
    {
        for (int i = 0; i < vertices.length; i++)
        {
            if (vertices[i].port == port)
                return i;
        }
        return -1;
    }

    /**
     * Helper function for buildTable()
     * 
     * @param vertices
     * @return
     */
    private int findMin(Vertex[] vertices)
    {
        int result = 0, min = Integer.MAX_VALUE;
        for (int i = 0; i < vertices.length; i++)
        {
            int distance = vertices[i].distance;
            if (!vertices[i].visited && distance >= 0 && distance < min)
            {
                result = i;
                min = distance;
            }
        }
        return result;
    }

    /**
     * Start the verification process on this node.
     */
    private void verify()
    {
        verifyFinished = true;
        for (int neighbour : neighbours.keySet())
        {
            if (!verified.get(neighbour))
            {
                Packet packet = new Packet(Packet.PacketType.Verify, neighbours.get(neighbour));
                port.send(packet, localhost, neighbour);
                new Thread(new WaitVerifyACK(neighbour)).start();
            }
        }
    }

    /**
     * Constructor, taking the command line parameters.
     * 
     * @param args
     *            Command line parameters from main functions.
     */
    public lsnode(String[] args)
    {
        localPort = Integer.parseInt(args[0]);
        isLast = args[args.length - 1].equals("last");
        for (int i = 1; i < args.length - 1; i += 2)
        {
            int port = Integer.parseInt(args[i]);
            int distance = Integer.parseInt(args[i + 1]);

            neighbours.put(port, distance);
            verified.put(port, false);
            recvedDVec.put(localPort, neighbours);
        }

        try
        {
            port = new UDPWrapper(localPort);
        }
        catch (SocketException e)
        {
            System.out.println("Port in use, exiting...");
        }
    }

}
